This invention is generally related to computer systems and more particularly to techniques for avoiding deadlock when performing bus transactions from an outbound pipe of a bridge.
Computer systems use a bridge between two buses to allow devices on one bus to communicate with devices on the other bus. FIG. 1 shows such a conventional computer system 102 which complies with the popular Peripheral Components Interconnect (PCI) Specification, Revision 2.1, Jun. 1, 1995. The system 102 has a processor 104, which in certain cases is called the host processor, coupled to a host bus 105. A memory 112 normally comprising Dynamic Random Access Memory (DRAM) stores programs to be executed by the processor. The memory can be accessed by the processor 104 via a chip set 108 which provides transfer logic for transactions between the host bus 105 and a PCI bus 116 and between the PCI bus 116 and the memory 112. An I/O bridge 124 gives access to a legacy bus 128.
The following example illustrates the problem of deadlock encountered when performing multiple types of bus transactions. The chip set 108 can process multiple transactions using a pipe. FIG. 2 shows the status of an inbound pipe 130 and an outbound pipe 134. Also shown are outbound pipes 138 and 142 in the I/O bridge 124 and PCI device 120, respectively. The pipes contain several pending requests for transactions which have resulted in a deadlock condition.
Each outbound pipe has a number of entries where each entry can hold transaction information (e.g., request packets containing target address and command information) and transaction data (e.g., data packets containing the transaction data) for posted and non-posted transactions. Posted writes include P-Writes 1 through 3. P-Writes 1 and 2 were initiated by the processor 104 and are directed at a target, e.g. the I/O bridge 124 or the PCI device 120, on the PCI bus 116. P-Writes 1 and 2 are known as downstream transactions. In contrast, P-Write 3 was initiated on the legacy bus 128 and is directed at the main memory 112. Thus, P-Write 3 is an upstream transaction. Examples of non-posted transactions are NP Read 1 in pipe 134 and NP Read 2 in pipe 142. An outbound pipe may also hold return data (as data packets) for a non-posted transaction, such as Read Return 1a and 1b in pipe 138, Read Return 2 in pipe 134, and Read Return 1 in pipe 142.
Normally, each PCI resource has both an inbound and outbound pipe. The inbound pipe 130 is used to store request packets for upstream non-posted read transactions, return data for downstream non-posted transactions (e.g., Read Return 1a for NP Read 1 in the chip set 108), and requests and associated data for upstream posted write transactions. All of the read return data, as specified in the non-posted read transaction, must be received by the chip set and held in an inbound pipe before it is made available to the processor which returns to fetch it.
Although not yet completed, P-Write 3 is targeting the chip set 108 such that the data for this transaction would be stored in the inbound pipe 130 when completed. The transaction information and data stored in the inbound and outbound pipes are processed in a first in first out (FIFO) manner. Thus, for example, in outbound pipe 134, NP Read 1 must be completed before any subsequent transactions or data, such as P-Write 1, in the pipe 134 can be performed on the PCI bus 116.
Two different deadlock conditions are illustrated in FIG. 2. In the first deadlock condition, the pipe 134 has requested read data for the NP Read 1 transaction, directed at the I/O bridge 124. The outbound pipe 138 of the bridge 124 has delivered part of the read data as Read Return 1a to the inbound pipe 130. However, the second part of the read data, Read Return 1b , became available after P-Write 3 was enqueued in the pipe 138. Thus, any further requests for NP Read 1 by the outbound pipe 134 will be signaled a retry, because P-Write 3 is blocking the pipe 138. Also, any requests for P-Write 3 by the pipe 138 are signaled a retry, because NP Read 1 is blocking the inbound pipe 130. As a result, no data can be transferred to or from the chip set 108 and the I/O bridge 124.
The second deadlock condition illustrated in FIG. 2 occurs when NP Read 1 is directed at PCI device 120 rather than at the I/O bridge 124. The Read Return 1 data for that transaction, however, became available after NP Read 2 was enqueued in the outbound pipe 142 of the PCI device 120. Thus, any requests for NP Read 1 are signaled a retry, because NP Read 2 is blocking pipe 142. Similarly, any requests for NP Read 2 are signaled a retry, because NP Read 1 is blocking pipe 134. Once again, no data can be transferred to and from chip set 108.
One way to avoid the above-described first deadlock condition is to configure a PCI resource as to preclude any posted write from entering the resource's outbound pipe when a non-posted read request has been received over the bus and read return data for that read have not all been completed to the requesting master. A different way to avoid the second deadlock condition is to configure the PCI resource to time out the NP Read at the head of its outbound pipe after a large number of retried attempts. Upon the time out event, the NP Read request packet is discarded from the head of the outbound pipe and the discard status is communicated to control logic at the other side of the pipe to re-issue the same NP Read request. However, the first deadlock-avoidance technique fails to make optimal use of the full capacity of the outbound pipe because the pipe is permitted to hold only the single, non-posted read return. The second deadlock avoidance technique described above is performance-limiting as it allows the NP Read transaction at the head of the outbound pipe to be fruitlessly attempted for a relatively long time at the expense of blocking progress of transactions behind the NP Read and causing the pipe to back up. Therefore, there is a need for a technique of avoiding deadlocks that makes efficient use of the outbound pipe.